package tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 计算给定二叉树的所有左叶子之和。
 * @author le
 */
public class SumOfLeftLeaves
{
    public static void main(String[] args)
    {

    }

    public int sumOfLeftLeaves(TreeNode root) {
        // 创建队列用于广搜
        Queue<TreeNode> queue = new LinkedList<>();
        int res = 0;
        if (root != null){
            queue.add(root);
        }
        // 循环遍历
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if (node.left != null){
                // 判断左节点 是不是 叶子结点
                if (isLeafNode(node.left)){
                    res += node.left.val;
                }else{
                    // 如果不是叶子结点 加入队列
                    queue.offer(node.left);
                }
            }

            // 注意这里是不做 加操作的 因为是求 左子叶的和
            // 当不是 叶子结点时 只需要将右节点 送入队列即可
            if (node.right != null){
                if (!isLeafNode(node.right)){
                    queue.offer(node.right);
                }
            }

        }
        return res;
    }

    /**
     * 用来判断是否是叶子结点
     * @param node
     * @return
     */
    public boolean isLeafNode(TreeNode node){
        return node.left == null && node.right == null;
    }

}
